﻿#define _CRT_SECURE_NO_WARNINGS 1

#include<stdio.h>
#include<stdlib.h>
#include<time.h>

void print(int* a, int n)
{
	for (int i = 0; i < n; i++)
	{
		printf("%d ", a[i]);
	}
	printf("\n");
}


void swap(int* a, int* b)
{
	int c = *a;
	*a = *b;
	*b = c;
}

//冒泡排序 O(N^2)
void bubblesort(int* a, int n)
{
	for (int f = 1; f < n; f++)
	{
		for (int i = 0; i < n - f; i++)
		{
			if (a[i] > a[i + 1])
			{
				swap(a + i, a + i + 1);
			}
		}
	}
}

//插入 O(N^2)
void insertsort(int* a, int n)
{
	for (int i = 0; i < n - 1; i++)
	{
		int end = i;
		int tmp = a[end + 1];
		while (end >= 0)
		{
			if (tmp < a[end])
			{
				a[end + 1] = a[end];
				end--;
			}
			else
			{
				break;
			}
		}
		a[end + 1] = tmp;
	}

}

//shell排序 O(N*logN)
void shellsort(int* a, int n)
{
	int gap = n;
	while (gap > 1)
	{
		gap = gap / 3 + 1;
		for (int i = 0; i < n - gap; i++)
		{
			int end = i;
			int tmp = a[end + gap];
			while (end >= 0)
			{
				if (tmp < a[end])
				{
					a[end + gap] = a[end];
					end -= gap;
				}
				else
				{
					break;
				}
			}
			a[end + gap] = tmp;
		}
	}
}

// 堆排序 O(N*logN)
void AdjustDown(int* arr, int n, int parent)
{
	int child = parent * 2 + 1;
	while (child < n)
	{
		if (child + 1 < n && arr[child + 1] > arr[child])
		{
			child++;
		}
		if (arr[child] > arr[parent])
		{
			swap(arr + child, arr + parent);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}


void HeapSort(int* nums, int n)
{
	for (int i = (n - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(nums, n, i);
	}

	while (n > 1)
	{
		swap(nums + n - 1, nums);
		n--;
		AdjustDown(nums, n, 0);
	}
}

int middle(int* a, int left, int right)
{
	int midi = (left + right) / 2;
	if (a[left] < a[midi])
	{
		if (a[right] > a[midi])
		{
			return midi;
		}
		else if (a[right] > a[left])
		{
			return right;
		}
		else
		{
			return left;
		}
	}
	else
	{
		if (a[midi] > a[right])
		{
			return midi;
		}
		else if (a[left] > a[right])
		{
			return right;
		}
		else
		{
			return left;
		}
	}
}

//huare版本
//快速排序 O(N*logN)
void QuickSort1(int* a, int left, int right)
{
	if (left >= right)
	{
		return;
	}

	int keyi = left;
	int begin = left, end = right;

	//三数取中
	//int midi = middle(a, left, right);
	//swap(a + left, a + midi);

	//选区间中的随机数做 keyi
	//int midi = left + rand() % (right - left);
	//swap(a + midi, a + keyi);

	while (left < right)
	{
		while (a[right] >= a[keyi] && right > left)
		{
			right--;
		}
		while (a[left] <= a[keyi] && left < right)
		{
			left++;
		}
		swap(&a[left], &a[right]);
	}

	swap(&a[left], &a[keyi]);

	QuickSort1(a, begin, left - 1);
	QuickSort1(a, left + 1, end);
}

void testQuickSort1()
{
	int arr[] = { 1,3,5,7,9,0,8,6,5,4,3,2 };
	QuickSort1(arr, 0, sizeof(arr) / sizeof(int) - 1);
}

//挖坑法
//O(N*logN)
void QuickSort2(int* a, int left, int right)
{
	if (left >= right)
	{
		return;
	}

	//三数取中
	int midi = middle(a, left, right);
	swap(a + left, a + midi);

	int key = a[left];
	int begin = left, end = right;
	while (left < right)
	{
		while (a[right] > key && left < right)
		{
			right--;
		}
		a[left] = a[right];

		while (a[left] <= key && left < right)
		{
			left++;
		}
		a[right] = a[left];
	}

	a[left] = key;

	QuickSort2(a, begin, left - 1);
	QuickSort2(a, left + 1, end);
}


void testQuickSort2()
{
	//int arr[] = { 1,3,5,7,9,0,8,6,5,4,3,2 };
	int arr[] = { 1,2,3,4,5,6,6,7,8,9 };
	QuickSort2(arr, 0, sizeof(arr) / sizeof(int) - 1);
}

void QuickSort3(int* a, int left, int right)
{
	if (left > right)
	{
		return;
	}

	//三数取中
	int midi = middle(a, left, right);
	swap(a + left, a + midi);
	int cur = left + 1;
	int prev = left;
	int keyi = left;

	while (cur <= right)
	{
		if (a[cur] <= a[keyi] && ++prev != cur)
		{
			swap(a + cur, a + prev);
		}
		cur++;
	}

	swap(a + keyi, a + prev);
	QuickSort3(a, prev + 1, right);
	QuickSort3(a, left, prev - 1);
}


void testQuickSort3()
{
	int arr[] = { 1,3,5,7,9,0,8,6,5,4,3,2 };
	//int arr[] = { 1,2,3,4,5,6,6,7,8,9 };
	QuickSort3(arr, 0, sizeof(arr) / sizeof(int) - 1);
}

void TestOP()
{
	srand(time(0));
	const int N = 1000000;
	int* a1 = (int*)malloc(sizeof(int) * N);
	int* a2 = (int*)malloc(sizeof(int) * N);
	int* a3 = (int*)malloc(sizeof(int) * N);
	int* a4 = (int*)malloc(sizeof(int) * N);
	int* a5 = (int*)malloc(sizeof(int) * N);
	int* a6 = (int*)malloc(sizeof(int) * N);
	for (int i = 0; i < N; ++i)
	{
		a1[i] = rand();
		//a1[i] = i;
		a2[i] = a1[i];
		a3[i] = a1[i];
		a4[i] = a1[i];
		a5[i] = a1[i];
		a6[i] = a1[i];
	}
	//int begin1 = clock();
	//insertsort(a1, N);
	//int end1 = clock();

	int begin2 = clock();
	shellsort(a2, N);
	int end2 = clock();

	int begin4 = clock();
	HeapSort(a4, N);
	int end4 = clock();

	int begin5 = clock();
	QuickSort3(a5, 0, N - 1);
	int end5 = clock();

	//printf("InsertSort:%d\n", end1 - begin1);
	printf("ShellSort:%d\n", end2 - begin2);
	printf("HeapSort:%d\n", end4 - begin4);
	printf("QuickSort:%d\n", end5 - begin5);
	free(a1);
	free(a2);
	free(a3);
	free(a4);
	free(a5);
	free(a6);
}


int main1()
{
	//testQuickSort1();
	//testQuickSort2();
	//testQuickSort3();
	TestOP();
	return 0;
}

